// class Solution
// {
//     int m, n, k;
//     bool vis[101][101];
//     int ret;
//     int dx[4] = {0, 0, -1, 1};
//     int dy[4] = {1, -1, 0, 0};

// public:
//     int movingCount(int _m, int _n, int _k)
//     {
//         m = _m, n = _n, k = _k;
//         dfs(0, 0);
//         return ret;
//     }

//     void dfs(int i, int j)
//     {
//         ret++;
//         vis[i][j] = true;
//         for (int k = 0; k < 4; k++)
//         {
//             int x = i + dx[k], y = j + dy[k];
//             if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && check(x, y))
//                 dfs(x, y);
//         }
//     }
//     bool check(int i, int j)
//     {
//         int tmp = 0;
//         while (i)
//         {
//             tmp += i % 10;
//             i /= 10;
//         }
//         while (j)
//         {
//             tmp += j % 10;
//             j /= 10;
//         }
//         return tmp <= k;
//     }
// };